// Copyright 2013 Daniel de Kok
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.gitee.wsl.text.dictomaton.levenshtein


import com.gitee.wsl.collections.list.LinkedList
import com.gitee.wsl.ext.base.Character
import com.gitee.wsl.ext.base.Integer
import com.gitee.wsl.ext.list.poll
import com.gitee.wsl.ext.list.pollOrNull
import com.gitee.wsl.ext.string.charAt
import com.gitee.wsl.text.dictomaton.Dictionary
import com.gitee.wsl.text.format.format
import kotlin.invoke
import kotlin.math.min
import kotlin.text.iterator

/**
 * A Levenshtein automaton is an automaton that accepts a string and all strings within
 * a given edit distance. This class constructs the automaton from parametric state/transition
 * tables, allowing for the construction of the automaton in *O(l*n)* time, where *l*
 * is the word length and *n* the number of edit operations. In other words, the construction
 * time grows linearly with the length of a word for a given edit distance.
 */
class LevenshteinAutomaton(word: String, maxDistance: Int) {
    private val d_startState: LevenshteinAutomatonState
    private val d_alphabet: Set<Character>
    private val d_otherChar: Char

    /**
     * Construct a Levenshtein automaton for a word with a maximumum permitted Levenshtein
     * distance. The maximum distance can currently be 1 or 2.
     *
     * @param word        The word.
     * @param maxDistance The maximum distance.
     */
    init {
        if (maxDistance > d_parametricTransitions.size || maxDistance < 1) throw IllegalArgumentException(
            String.format(
                "The maximum supported edit distance is: %d",
                d_parametricTransitions.size
            )
        )

        d_alphabet = extractAlphabet(word)
        d_otherChar = findAnyChar(d_alphabet)
        d_alphabet.add(d_otherChar)

        d_startState = createAutomaton(
            d_parametricTransitions[maxDistance - 1],
            word
        )
        d_startState.reduce(d_otherChar)
    }

    /**
     * Return the automaton in Graphviz dot format.
     *
     * @return Dot representation.
     */
    fun toDot(): String {
        val stringBuilder = StringBuilder()
        stringBuilder.append("digraph G {\n")

        val stateNumbers = numberedStates(d_startState)

        // We want to traverse states a fixed order, so that the output is predictable. We
        // could also store the numbered states in a TreeMap, but LevenshteinAutomatonState doesn't implement
        // Comparable, and I wouldn't even know what that would mean ;).
        val states: Array<LevenshteinAutomatonState?> = arrayOfNulls<LevenshteinAutomatonState>(stateNumbers.size)

        for (numberedState in stateNumbers.entries) states[numberedState.value] = numberedState.key

        for (stateNumber in states.indices) {
            val s= states[stateNumber]!!

            if (s.isFinal) stringBuilder.append(String.format("%d [peripheries=2];\n", stateNumber))

            for (trans in s.transitions.entries) stringBuilder.append(
                String.format(
                    "%d -> %d [label=\"%c\"];\n", stateNumber,
                    stateNumbers.get(trans.value), trans.key
                )
            )
        }

        stringBuilder.append("}")

        return stringBuilder.toString()
    }

    /**
     * Compute the intersection language of a dictionary and the automaton. This amounts
     * to finding the strings in the dictionary that are within the edit distance allowed
     * by the [LevenshteinAutomaton].
     *
     * @param dictionary
     * @return The intersection language.
     */
    fun intersectionLanguage(dictionary: Dictionary): Set<String> {
        val language = HashSet<String>()

        val q/*: Queue<StatePair?>*/ = LinkedList<StatePair>()
        q.add(
            StatePair(
                dictionary.startState(),
                d_startState,
                ""
            )
        )

        while (!q.isEmpty()) {
            val pair: StatePair = q.poll()
            val dictState = pair.dictionaryState
            val laState: LevenshteinAutomatonState = pair.levenshteinAutomatonState
            val string = pair.string

            for (c in dictionary.transitionCharacters(dictState)) {
                var laNewState = laState.move(c)

                if (laNewState == null && (laState.move(d_otherChar).also { laNewState = it }) == null) continue

                val dictNewState: Int = dictionary.next(dictState, c)

                val newString = string + c

                if (laNewState!!.isFinal  && dictionary.isFinalState(dictNewState)) language.add(newString)

                q.add(
                    StatePair(
                        dictNewState,
                        laNewState,
                        newString
                    )
                )
            }
        }

        return language
    }

    /**
     * Create the Levenshtein automaton for a word.
     *
     * @param transitions The parametric transition table.
     * @param word        The word.
     * @return
     */
    private fun createAutomaton(transitions: ParametricTransitions, word: String): LevenshteinAutomatonState {
        val n: Int = transitions.nEditOperations()

        val states: Array<LevenshteinAutomatonState> = Array<LevenshteinAutomatonState>(
            (word.length + 1) * transitions.nParametricStates()
        ){ LevenshteinAutomatonState()}
        //for (i in states.indices) states[i] = LevenshteinAutomatonState()

        val nParametricStates: Int = transitions.nParametricStates()
        val lastPosition = states.size / nParametricStates

        // Fill state table.
        for (i in states.indices) {
            val offset: Int = i / nParametricStates
            val parametricState: Int = i % nParametricStates

            for (c in d_alphabet) {
                val vec = characteristicVector(word, offset, c, n)

                // Will be handled by the 'other' transition.
                if (vec == 0 && c != d_otherChar) continue

                val toState: Int = transitions.transition(parametricState, offset, vec, word.length)
                if (toState != -1) states[i].addTransition(c, states[toState])
            }

            if (lastPosition - 1 - offset <= transitions.maxOffsetErrors(parametricState)) states[i].isFinal = true
        }

        return states[0]
    }

    private fun characteristicVector(word: String, offset: Int, c: Char, n: Int): Int {
        val vlen: Int = min(2 * n + 1, word.length - offset)

        var vec = 0
        for (i in 0..<vlen) {
            vec = vec shl 1
            vec = vec or if (word.charAt(offset + i) ==c) 1 else 0
        }

        return vec
    }

    private fun extractAlphabet(word: String): MutableSet<Character> {
        val alphabet = HashSet<Char>()

        for (i in 0..<word.length) alphabet.add(word.charAt(i))

        return alphabet
    }

    private fun findAnyChar(alphabet: Set<Character>): Char {
        for (c in 0..< Character.MAX_VALUE.code) {
            val ca = c.toChar()
            if (!alphabet.contains(ca)) return ca
        }

        throw IllegalArgumentException("At least one character that is not in the alphabet is required.")
    }

    private fun numberedStates(startState: LevenshteinAutomatonState): Map<LevenshteinAutomatonState, Integer> {
        val states = HashMap<LevenshteinAutomatonState, Integer>()

        val stateQueue/*: Queue<LevenshteinAutomatonState?> */= LinkedList<LevenshteinAutomatonState>()
        stateQueue.add(startState)
        while (!stateQueue.isEmpty()) {
            val s: LevenshteinAutomatonState = stateQueue.poll()

            if (states.containsKey(s)) continue

            states.put(s, states.size)

            for (to in s.transitions.values) stateQueue.add(to)
        }

        return states
    }

    /**
     * This class stores a pair of states from a [LevenshteinAutomaton] and a [Dictionary].
     */
    private inner class StatePair(val dictionaryState: Int, laState: LevenshteinAutomatonState, val string: String?) {
        private val d_laState: LevenshteinAutomatonState = laState

        val levenshteinAutomatonState: LevenshteinAutomatonState
            get() = d_laState
    }

    companion object {
        private val d_parametricTransitions: Array<ParametricTransitions> = arrayOf<ParametricTransitions>(
            ParametricTransitions1(),
            ParametricTransitions2()
        )
    }
}
